package Demo4;

import java.util.Stack;

/**
 * @ClassName Matching
 * @Description 括号匹配问题
 * @Author ZJX
 * @Date 2024/9/18 11:51
 * @Version 1.0
 */
public class Matching {
    public boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<>();  // 用栈来存储左括号
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);  // 遇到左括号，压入栈中
            } else if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if (!isMatchingPair(top, ch)) {
                    return false;
                }
            }

        }

        return stack.isEmpty();  // 检查栈是否为空
    }

    private boolean isMatchingPair(char open, char close) {
        return (open == '(' && close == ')') || (open == '{' && close == '}') || (open == '[' && close == ']');
    }


    public static void main(String[] args) {
        Matching matching = new Matching();
        String expression1 = "(1 + 2) * (3 / (4 - 5))";
        String expression2 = "((1 + 2) * (3 / (4 - 5))"; // 少个括号 false;
        String expression3 = "1 + 2 * 3";  // 没有括号
        System.out.println(matching.isValidParentheses(expression1));
        System.out.println(matching.isValidParentheses(expression2));
        System.out.println(matching.isValidParentheses(expression3));
    }
}
